#include<vector>
#include<time.h>
using namespace std;
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // int n=nums.size(),key=n/2;
        srand(NULL);
        patition(nums, 0, nums.size() - 1);
        return nums;
    }
    int randrom(vector<int>& nums, int l, int r) {
        int ret = rand();
        return nums[ret % (r - l + 1) + l];
    }
    void patition(vector<int>& nums, int left, int right) {

        if (left >= right)
            return;
        int key = randrom(nums, left, right);
        int l = left - 1, r = right + 1, i = left;
        while (i < r) {
            if (nums[i] < key)
                swap(nums[++l], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--r], nums[i]);
        }
        // 
        patition(nums, left, l);
        patition(nums, r, right);
    }
};

